﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Katamino
{
    public class BitFinder
    {
        private int[] _cache;

        public BitFinder()
        {
            _cache = new int[256];
        }

        /// <summary>
        /// Sequentially return all bits set in
        /// </summary>
        /// <param name="_v"></param>
        /// <returns></returns>
        public IEnumerable<int> EnumerateBits(UInt64 _v)
        {
            UInt64 c = _v;

            for (int i = 0; c > 0; i++, c = (c>>1))
            {
                if ((c & 1) == 1)
                    yield return i;
            }

            yield break;
        }

        /// <summary>
        /// Find the 0 based index of the first bit set in UInt64.
        /// </summary>
        /// <param name="_v"></param>
        /// <returns>
        /// -1 for no bit set (_v = 0),
        /// 0..63 otherwise
        /// </returns>
        public int FindBit(UInt64 _v)
        {
            int result = 0;

            // try for trivial case that no bit is set at all
            if (_v == (UInt64)0) return -1;

            // prepare for bitshift if it is not expected to be found in the cache
            while (((_v & 255) == 0) && (_v > 0))
            {
                result = result + 8;
                _v = (_v >> 8);
            }

            // Try for a cache value. Remind, that in the cache, 0 means an empty cache entry, and 1 is the first bit.
            int _cacheindex = (int)(_v & 255);

            if (_cache[_v & 255] > 0) return (_cache[_v] - 1); // the return value should be 0..7

            // No cache hit, so we have to calculate and store in cache
            // we know we have at least one bit set.
            if ((_v & 15) == 0)
            {
                result += 4;
                _v >>= 4;
            }
            if ((_v & 3) == 0)
            {
                result += 2;
                _v >>= 2;
            }
            if ((_v & 1) == 0)
            {
                result += 1;
            }

            _cache[_cacheindex] = result + 1;

            return result;
        }

        /// <summary>
        /// Find the zero based index of the first bit set to 0. Inverse of FindBit
        /// </summary>
        /// <param name="_v"></param>
        /// <returns></returns>
        public int FindZero(UInt64 _v)
        {
            return FindBit(~_v);
        }
    }
}
